package study.search;

import java.util.Arrays;

public class FibSearch {
    public static int maxSize = 20;

    public static void main(String[] args) {
        int[] arr = {1, 8, 10, 89, 1000, 1234};
        int i = fibSearch(arr, 1234);
        System.out.println("index=" + i);

    }

    /**
     * 构建一个斐波那契数列
     * @return
     */
    public static int[] fibArray() {
        int[] f = new int[maxSize];
        f[0] = 1;
        f[1] = 1;
        for (int i = 2; i < maxSize; i++) {
            f[i] = f[i-1] + f[i-2];
        }
        return f;
    }

    public static int fibSearch(int[] arr, int findValue){
        int lowIndex = 0;
        int highIndex = arr.length - 1;
        int midIndex = 0;
        //存放下标为mid的值
        int midValue = 0;
        //获取斐波那契数列
        int[] fib = fibArray();
        //arr = {1, 8, 10, 1000, 1234}
        //fib = {1, 1, 2, 3, 5, 8, 13, 21, 44, ...}
        //获取斐波那契数列分割数值的下标
        while (highIndex > fib[midIndex] - 1){
            midIndex++;
        }
        //创建一个临时数组 tempArr = {1, 8, 10, 1000, 1234, 1234, 1234}
        int[] tempArr = Arrays.copyOf(arr, fib[midIndex] - 1);
        //使用arr数组最后的数填充tempArr
        //tempArr = {1, 8, 10, 1000, 1234, 1234, 1234}
        for (int i = highIndex + 1; i < tempArr.length; i++) {
            tempArr[i] = arr[highIndex];
        }

        //遍历寻找findValue
        while (lowIndex <= highIndex){
            midValue = lowIndex + fib[midIndex - 1] - 1;
            //先查找左边的值

            if (findValue < tempArr[midValue]){
                highIndex = midValue - 1;
                midIndex--;
            } else if(findValue > tempArr[midValue]){
                lowIndex = midValue + 1;
                midIndex -= 2;
            } else {
                // 找到
                // 需要确定返回那个下标
                if (midValue <= highIndex){
                    return midValue;
                }else {
                    return highIndex;
                }
            }
        }

        return -1;
    }
}
